1. Technical Field
The present invention relates in general to content addressable memory (CAM), and more particularly, to a circuit for reading out multiple match hits from a CAM.
2. Background Art
A content addressable memory (CAM) includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory cells in the CAM constitute a CAM word. During compare (i.e., xe2x80x9csearchxe2x80x9d) operations, a comparand word is received at appropriate input terminals of the CAM and then simultaneously compared in parallel to all the CAM words in the CAM. If the comparand word matches one of the CAM words (i.e., a matchline xe2x80x9chitxe2x80x9d occurs), a matchline corresponding to the matching CAM word is asserted to indicate a match condition. If the comparand word matches more than one of the CAM words, the matchline corresponding to each of the matching CAM words is asserted, and a xe2x80x9cmultiple matchxe2x80x9d flag is asserted to indicate the multiple match condition.
The asserted matchline(s) are prioritized in a predetermined manner and subsequently decoded into their corresponding CAM addresses using a priority encoder. When multiple matches are present, the time required to examine and encode all of the addresses corresponding to the asserted matchlines is dependent upon the minimum cycle time between address reads. In particular, the greater the minimum cycle time, the longer it takes the priority encoder to encode all of the addresses corresponding to the asserted matchlines.
An example of a system for reading multiple matched addresses is disclosed in U.S. Pat. No. 6,118,682 to Martin, which is incorporated herein by reference. In Martin, the signal level of every matchline of the CAM must be tested in succession with the addition of a gate delay, whether matching or not. The minimum cycle time in this system is limited by the AND gate delay of a signal rippling through a plurality of AND gates (see, e.g., AND gates 26, 28, 30, . . . , FIG. 1 of Martin). Since, for each matchline of the CAM, another AND gate is required, the minimum cycle time increases dramatically as the size of the CAM increases. In particular, the minimum cycle time in Martin is given by:
min_cycle=gate delay*#of matchlines. 
As an example, for a 16-word CAM, the minimum cycle time (gate delays) is 16, while for a 1024-word CAM, the minimum cycle time (gate delays) is 1024.
As a result, there exists a need for a circuit for reading out multiple match hits from a CAM in a more time efficient manner. In particular, there exists a need for a circuit for reading out multiple match hits from a CAM that reduces the minimum cycle time between address reads.
A first aspect of the invention provides an apparatus for reading out multiple match hits from a content addressable memory (CAM), comprising a priority encoder for receiving a plurality of matchlines from a CAM and for encoding addresses of the CAM that are associated with the matchlines that indicate a match, and a matchline mask system for selectively masking off a matchline that indicates a match from the priority encoder after the address associated with that matchline is encoded by the priority encoder.
A second aspect of the invention provides an apparatus for masking matchlines of a content addressable memory (CAM), comprising a plurality of matchline mask units, wherein each matchline of the CAM passes through a respective one of the matchline mask units, and wherein each matchline mask unit is configured to mask its associated matchline from a priority encoder, and a decoder system for sequentially masking each matchline that indicates a match from the priority encoder using the matchline""s respective matchline mask unit.
A third aspect of the invention provides a method for reading out multiple match hits from a content addressable memory (CAM), comprising receiving a plurality of matchlines from a CAM, determining and prioritizing the matchlines that indicate a match, sequentially encoding the addresses of the CAM that are associated with the matchlines that indicate a match, and selectively masking off a matchline that indicates a match after the address associated with that matchline has been encoded.
The exemplary aspects of the present invention are designed to solve the problems herein described and other problems not discussed, which are discoverable by a skilled artisan.